<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-pragma">{-# LANGUAGE CPP #-}</span><span class="hs-cpp">
#if !defined(TESTING) &amp;&amp; defined(__GLASGOW_HASKELL__)
</span><span class="hs-pragma">{-# LANGUAGE Safe #-}</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">
#include &quot;containers.h&quot;
</span><span>
</span><span id="line-8"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-9"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-10"></span><span class="hs-comment">-- Module      :  Data.IntSet</span><span>
</span><span id="line-11"></span><span class="hs-comment">-- Copyright   :  (c) Daan Leijen 2002</span><span>
</span><span id="line-12"></span><span class="hs-comment">--                (c) Joachim Breitner 2011</span><span>
</span><span id="line-13"></span><span class="hs-comment">-- License     :  BSD-style</span><span>
</span><span id="line-14"></span><span class="hs-comment">-- Maintainer  :  libraries@haskell.org</span><span>
</span><span id="line-15"></span><span class="hs-comment">-- Portability :  portable</span><span>
</span><span id="line-16"></span><span class="hs-comment">--</span><span>
</span><span id="line-17"></span><span class="hs-comment">--</span><span>
</span><span id="line-18"></span><span class="hs-comment">-- = Finite Int Sets</span><span>
</span><span id="line-19"></span><span class="hs-comment">--</span><span>
</span><span id="line-20"></span><span class="hs-comment">-- The @'IntSet'@ type represents a set of elements of type @Int@.</span><span>
</span><span id="line-21"></span><span class="hs-comment">--</span><span>
</span><span id="line-22"></span><span class="hs-comment">-- For a walkthrough of the most commonly used functions see their</span><span>
</span><span id="line-23"></span><span class="hs-comment">-- &lt;https://haskell-containers.readthedocs.io/en/latest/set.html sets introduction&gt;.</span><span>
</span><span id="line-24"></span><span class="hs-comment">--</span><span>
</span><span id="line-25"></span><span class="hs-comment">-- These modules are intended to be imported qualified, to avoid name</span><span>
</span><span id="line-26"></span><span class="hs-comment">-- clashes with Prelude functions, e.g.</span><span>
</span><span id="line-27"></span><span class="hs-comment">--</span><span>
</span><span id="line-28"></span><span class="hs-comment">-- &gt;  import Data.IntSet (IntSet)</span><span>
</span><span id="line-29"></span><span class="hs-comment">-- &gt;  import qualified Data.IntSet as IntSet</span><span>
</span><span id="line-30"></span><span class="hs-comment">--</span><span>
</span><span id="line-31"></span><span class="hs-comment">--</span><span>
</span><span id="line-32"></span><span class="hs-comment">-- == Performance information</span><span>
</span><span id="line-33"></span><span class="hs-comment">--</span><span>
</span><span id="line-34"></span><span class="hs-comment">-- Many operations have a worst-case complexity of /O(min(n,W))/.</span><span>
</span><span id="line-35"></span><span class="hs-comment">-- This means that the operation can become linear in the number of</span><span>
</span><span id="line-36"></span><span class="hs-comment">-- elements with a maximum of /W/ -- the number of bits in an 'Int'</span><span>
</span><span id="line-37"></span><span class="hs-comment">-- (32 or 64).</span><span>
</span><span id="line-38"></span><span class="hs-comment">--</span><span>
</span><span id="line-39"></span><span class="hs-comment">--</span><span>
</span><span id="line-40"></span><span class="hs-comment">-- == Implementation</span><span>
</span><span id="line-41"></span><span class="hs-comment">--</span><span>
</span><span id="line-42"></span><span class="hs-comment">-- The implementation is based on /big-endian patricia trees/.  This data</span><span>
</span><span id="line-43"></span><span class="hs-comment">-- structure performs especially well on binary operations like 'union'</span><span>
</span><span id="line-44"></span><span class="hs-comment">-- and 'intersection'.  However, my benchmarks show that it is also</span><span>
</span><span id="line-45"></span><span class="hs-comment">-- (much) faster on insertions and deletions when compared to a generic</span><span>
</span><span id="line-46"></span><span class="hs-comment">-- size-balanced set implementation (see &quot;Data.Set&quot;).</span><span>
</span><span id="line-47"></span><span class="hs-comment">--</span><span>
</span><span id="line-48"></span><span class="hs-comment">--    * Chris Okasaki and Andy Gill,  \&quot;/Fast Mergeable Integer Maps/\&quot;,</span><span>
</span><span id="line-49"></span><span class="hs-comment">--      Workshop on ML, September 1998, pages 77-86,</span><span>
</span><span id="line-50"></span><span class="hs-comment">--      &lt;http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452&gt;</span><span>
</span><span id="line-51"></span><span class="hs-comment">--</span><span>
</span><span id="line-52"></span><span class="hs-comment">--    * D.R. Morrison, \&quot;/PATRICIA -- Practical Algorithm To Retrieve</span><span>
</span><span id="line-53"></span><span class="hs-comment">--      Information Coded In Alphanumeric/\&quot;, Journal of the ACM, 15(4),</span><span>
</span><span id="line-54"></span><span class="hs-comment">--      October 1968, pages 514-534.</span><span>
</span><span id="line-55"></span><span class="hs-comment">--</span><span>
</span><span id="line-56"></span><span class="hs-comment">-- Additionally, this implementation places bitmaps in the leaves of the tree.</span><span>
</span><span id="line-57"></span><span class="hs-comment">-- Their size is the natural size of a machine word (32 or 64 bits) and greatly</span><span>
</span><span id="line-58"></span><span class="hs-comment">-- reduces the memory footprint and execution times for dense sets, e.g. sets</span><span>
</span><span id="line-59"></span><span class="hs-comment">-- where it is likely that many values lie close to each other. The asymptotics</span><span>
</span><span id="line-60"></span><span class="hs-comment">-- are not affected by this optimization.</span><span>
</span><span id="line-61"></span><span class="hs-comment">--</span><span>
</span><span id="line-62"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-63"></span><span>
</span><span id="line-64"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">Data.IntSet</span><span> </span><span class="hs-special">(</span><span>
</span><span id="line-65"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Strictness properties</span></span><span>
</span><span id="line-66"></span><span>            </span><span class="annot"><span class="hs-comment">-- $strictness</span></span><span>
</span><span id="line-67"></span><span>
</span><span id="line-68"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Set type</span></span><span class="hs-cpp">
#if !defined(TESTING)
</span><span>              </span><span class="annot"><a href="Data.IntSet.Internal.html#IntSet"><span class="hs-identifier">IntSet</span></a></span><span>          </span><span class="hs-comment">-- instance Eq,Show</span><span class="hs-cpp">
#else
</span><span>              </span><span class="hs-identifier">IntSet</span><span class="hs-special">(</span><span class="hs-glyph">..</span><span class="hs-special">)</span><span>      </span><span class="hs-comment">-- instance Eq,Show</span><span class="hs-cpp">
#endif
</span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#Key"><span class="hs-identifier">Key</span></a></span><span>
</span><span id="line-75"></span><span>
</span><span id="line-76"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Construction</span></span><span>
</span><span id="line-77"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#empty"><span class="hs-identifier">empty</span></a></span><span>
</span><span id="line-78"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#singleton"><span class="hs-identifier">singleton</span></a></span><span>
</span><span id="line-79"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#fromList"><span class="hs-identifier">fromList</span></a></span><span>
</span><span id="line-80"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#fromAscList"><span class="hs-identifier">fromAscList</span></a></span><span>
</span><span id="line-81"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#fromDistinctAscList"><span class="hs-identifier">fromDistinctAscList</span></a></span><span>
</span><span id="line-82"></span><span>
</span><span id="line-83"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Insertion</span></span><span>
</span><span id="line-84"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#insert"><span class="hs-identifier">insert</span></a></span><span>
</span><span id="line-85"></span><span>
</span><span id="line-86"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Deletion</span></span><span>
</span><span id="line-87"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#delete"><span class="hs-identifier">delete</span></a></span><span>
</span><span id="line-88"></span><span>
</span><span id="line-89"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Generalized insertion/deletion</span></span><span>
</span><span id="line-90"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#alterF"><span class="hs-identifier">alterF</span></a></span><span>
</span><span id="line-91"></span><span>
</span><span id="line-92"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Query</span></span><span>
</span><span id="line-93"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#member"><span class="hs-identifier">member</span></a></span><span>
</span><span id="line-94"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#notMember"><span class="hs-identifier">notMember</span></a></span><span>
</span><span id="line-95"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#lookupLT"><span class="hs-identifier">lookupLT</span></a></span><span>
</span><span id="line-96"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#lookupGT"><span class="hs-identifier">lookupGT</span></a></span><span>
</span><span id="line-97"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#lookupLE"><span class="hs-identifier">lookupLE</span></a></span><span>
</span><span id="line-98"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#lookupGE"><span class="hs-identifier">lookupGE</span></a></span><span>
</span><span id="line-99"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#null"><span class="hs-identifier">IS.null</span></a></span><span>
</span><span id="line-100"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#size"><span class="hs-identifier">size</span></a></span><span>
</span><span id="line-101"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#isSubsetOf"><span class="hs-identifier">isSubsetOf</span></a></span><span>
</span><span id="line-102"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#isProperSubsetOf"><span class="hs-identifier">isProperSubsetOf</span></a></span><span>
</span><span id="line-103"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#disjoint"><span class="hs-identifier">disjoint</span></a></span><span>
</span><span id="line-104"></span><span>
</span><span id="line-105"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Combine</span></span><span>
</span><span id="line-106"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#union"><span class="hs-identifier">union</span></a></span><span>
</span><span id="line-107"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#unions"><span class="hs-identifier">unions</span></a></span><span>
</span><span id="line-108"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#difference"><span class="hs-identifier">difference</span></a></span><span>
</span><span id="line-109"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#%5C%5C"><span class="hs-operator">(\\)</span></a></span><span>
</span><span id="line-110"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#intersection"><span class="hs-identifier">intersection</span></a></span><span>
</span><span id="line-111"></span><span>
</span><span id="line-112"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Filter</span></span><span>
</span><span id="line-113"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#filter"><span class="hs-identifier">IS.filter</span></a></span><span>
</span><span id="line-114"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#partition"><span class="hs-identifier">partition</span></a></span><span>
</span><span id="line-115"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#split"><span class="hs-identifier">split</span></a></span><span>
</span><span id="line-116"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#splitMember"><span class="hs-identifier">splitMember</span></a></span><span>
</span><span id="line-117"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#splitRoot"><span class="hs-identifier">splitRoot</span></a></span><span>
</span><span id="line-118"></span><span>
</span><span id="line-119"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Map</span></span><span>
</span><span id="line-120"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#map"><span class="hs-identifier">IS.map</span></a></span><span>
</span><span id="line-121"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#mapMonotonic"><span class="hs-identifier">mapMonotonic</span></a></span><span>
</span><span id="line-122"></span><span>
</span><span id="line-123"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Folds</span></span><span>
</span><span id="line-124"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#foldr"><span class="hs-identifier">IS.foldr</span></a></span><span>
</span><span id="line-125"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#foldl"><span class="hs-identifier">IS.foldl</span></a></span><span>
</span><span id="line-126"></span><span>            </span><span class="annot"><span class="hs-comment">-- ** Strict folds</span></span><span>
</span><span id="line-127"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#foldr%27"><span class="hs-identifier">foldr'</span></a></span><span>
</span><span id="line-128"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#foldl%27"><span class="hs-identifier">foldl'</span></a></span><span>
</span><span id="line-129"></span><span>            </span><span class="annot"><span class="hs-comment">-- ** Legacy folds</span></span><span>
</span><span id="line-130"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#fold"><span class="hs-identifier">fold</span></a></span><span>
</span><span id="line-131"></span><span>
</span><span id="line-132"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Min\/Max</span></span><span>
</span><span id="line-133"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#findMin"><span class="hs-identifier">findMin</span></a></span><span>
</span><span id="line-134"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#findMax"><span class="hs-identifier">findMax</span></a></span><span>
</span><span id="line-135"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#deleteMin"><span class="hs-identifier">deleteMin</span></a></span><span>
</span><span id="line-136"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#deleteMax"><span class="hs-identifier">deleteMax</span></a></span><span>
</span><span id="line-137"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#deleteFindMin"><span class="hs-identifier">deleteFindMin</span></a></span><span>
</span><span id="line-138"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#deleteFindMax"><span class="hs-identifier">deleteFindMax</span></a></span><span>
</span><span id="line-139"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#maxView"><span class="hs-identifier">maxView</span></a></span><span>
</span><span id="line-140"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#minView"><span class="hs-identifier">minView</span></a></span><span>
</span><span id="line-141"></span><span>
</span><span id="line-142"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Conversion</span></span><span>
</span><span id="line-143"></span><span>
</span><span id="line-144"></span><span>            </span><span class="annot"><span class="hs-comment">-- ** List</span></span><span>
</span><span id="line-145"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#elems"><span class="hs-identifier">elems</span></a></span><span>
</span><span id="line-146"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#toList"><span class="hs-identifier">toList</span></a></span><span>
</span><span id="line-147"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#toAscList"><span class="hs-identifier">toAscList</span></a></span><span>
</span><span id="line-148"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#toDescList"><span class="hs-identifier">toDescList</span></a></span><span>
</span><span id="line-149"></span><span>
</span><span id="line-150"></span><span>            </span><span class="annot"><span class="hs-comment">-- * Debugging</span></span><span>
</span><span id="line-151"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#showTree"><span class="hs-identifier">showTree</span></a></span><span>
</span><span id="line-152"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#showTreeWith"><span class="hs-identifier">showTreeWith</span></a></span><span class="hs-cpp">

#if defined(TESTING)
</span><span>            </span><span class="hs-comment">-- * Internals</span><span>
</span><span id="line-156"></span><span>            </span><span class="hs-special">,</span><span> </span><span class="hs-identifier">match</span><span class="hs-cpp">
#endif
</span><span>            </span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-159"></span><span>
</span><span id="line-160"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html"><span class="hs-identifier">Data.IntSet.Internal</span></a></span><span> </span><span class="hs-keyword">as</span><span> </span><span class="annot"><span class="hs-identifier">IS</span></span><span>
</span><span id="line-161"></span><span>
</span><span id="line-162"></span><span class="hs-comment">-- $strictness</span><span>
</span><span id="line-163"></span><span class="hs-comment">--</span><span>
</span><span id="line-164"></span><span class="hs-comment">-- This module satisfies the following strictness property:</span><span>
</span><span id="line-165"></span><span class="hs-comment">--</span><span>
</span><span id="line-166"></span><span class="hs-comment">-- * Key arguments are evaluated to WHNF</span><span>
</span><span id="line-167"></span><span class="hs-comment">--</span><span>
</span><span id="line-168"></span><span class="hs-comment">-- Here are some examples that illustrate the property:</span><span>
</span><span id="line-169"></span><span class="hs-comment">--</span><span>
</span><span id="line-170"></span><span class="hs-comment">-- &gt; delete undefined s  ==  undefined</span><span>
</span><span id="line-171"></span></pre></body></html>